package datastructure.trie;

import java.util.TreeMap;

/**
 * @author XY
 * @version 1.0
 * @date 2021/12/28 9:16
 * @Description
 * MapSum() 初始化 MapSum 对象
 * void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
 * int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
 *
 */
public class Leet677 {
    class MapSum {

        private class Node{
            //如果一个node的value不为0，说明改该node是一个字符串的结尾
            public int value;
            //用map直接标识下一个节点的值，和指向的下一个节点
            public TreeMap<Character, Node> next;

            public Node(){
                this(0);
            }

            public Node(int value){
                this.value=value;
                next = new TreeMap<>();
            }
        }

        private Node root;

        public MapSum() {
            root = new Node();

        }

        public void insert(String word, int val) {
            Node cur = root;

            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                //如果不进入if则说明当前字符已经存在
                if(cur.next.get(c)==null){
                    cur.next.put(c,new Node());
                }
                cur = cur.next.get(c);
            }
            //循环结束后说明一个完整的单词插入成功，给这个单词赋值为val
            cur.value = val;

        }

        public int sum(String prefix) {
            //先查询根节点下面是否有该prefix，如果没有则直接返回0
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if(cur.next.get(c)==null){
                    return 0;
                }
                cur = cur.next.get(c);
            }
            //如果有，则递归求出所有后续节点的和，不是单词的val为0，不影响计算
            return sum(cur);
        }

        private int sum(Node node){
            //第一个value
            int res = node.value;
            //累加后面有value的值，没有的加0也不影响，如果没有子节点了，循环就进不去了，就会停止递归
            for (Character c : node.next.keySet()) {
                res += sum(node.next.get(c));
            }
            return res;
        }
    }

}
